#include<stdio.h>
#include<stdlib.h>
#include<string.h>

/*
 * Shell Sorting, derived from Insert Sorting
 */

void
shell_sort(int *arr, int len)
{
	int increment, i, j;
	int tmp;
	for(increment=(len>>1); increment>0; increment>>=1) {
		for(i=increment; i<len; i++) {
			tmp = arr[i];
			for(j=i; j>=increment; j-=increment) {
				if(arr[j-increment] > tmp)
					arr[j] = arr[j-increment];
				else
					break;
			}
			arr[j] = tmp;
		}
		int x;
		for(x=0; x<10; x++)
			printf("%d\t", arr[x]);
		printf("\n");
	}
}

int
main(int argc, char **argv)
{
	int arr[10] = {100, 3, 44, 56, 33, 1, 101, 88, 9, 11};

	shell_sort(arr, 10);

	int i;
}
